/**
 * Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 */
package com.xinpan.exercise;

import java.util.ArrayList;

public class InsertInterval {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<Interval> newList = new ArrayList<Interval>();
        if(intervals.size() == 0)
        {
            newList.add(newInterval);
            return newList;
        }
        int s;
        for(s = 0; s < intervals.size(); s++)
            if(newInterval.start <= intervals.get(s).end)
                break;
            else
                newList.add(intervals.get(s));
        
        int start = 0;
        if(s == intervals.size())
        {
            newList.add(newInterval);
            return newList;
        }
        if(newInterval.start < intervals.get(s).start)
            start = newInterval.start;
        else
            start = intervals.get(s).start;
        
        int e;
        for(e = s; e < intervals.size(); e++)
            if(newInterval.end < intervals.get(e).end)
                break;
        
        int end = 0;
        if(e == intervals.size())
            end = newInterval.end;
        else if(newInterval.end < intervals.get(e).start)
        {
            end = newInterval.end;
            e--;
        }
        else
            end = intervals.get(e).end;
        
        newList.add(new Interval(start, end));
        
        for(e++; e < intervals.size(); e++)
            newList.add(intervals.get(e));
            
        return newList;
    }
    
    class Interval {
    	      int start;
    	      int end;
    	      Interval() { start = 0; end = 0; }
    	      Interval(int s, int e) { start = s; end = e; }
    }
}
